home *** CD-ROM | disk | FTP | other *** search
/ Visual Cafe 3 / Visual Cafe 3.ISO / Vcafe / Main.bin / CompactCharArray.java < prev    next >
Text File  |  1998-09-22  |  15KB  |  421 lines
  1. /*
  2.  * @(#)CompactCharArray.java    1.9 97/10/28
  3.  *
  4.  * (C) Copyright Taligent, Inc. 1996 - All Rights Reserved
  5.  * (C) Copyright IBM Corp. 1996 - All Rights Reserved
  6.  *
  7.  * Portions copyright (c) 1996 Sun Microsystems, Inc. All Rights Reserved.
  8.  *
  9.  *   The original version of this source code and documentation is copyrighted
  10.  * and owned by Taligent, Inc., a wholly-owned subsidiary of IBM. These
  11.  * materials are provided under terms of a License Agreement between Taligent
  12.  * and Sun. This technology is protected by multiple US and International
  13.  * patents. This notice and attribution to Taligent may not be removed.
  14.  *   Taligent is a registered trademark of Taligent, Inc.
  15.  *
  16.  * Permission to use, copy, modify, and distribute this software
  17.  * and its documentation for NON-COMMERCIAL purposes and without
  18.  * fee is hereby granted provided that this copyright notice
  19.  * appears in all copies. Please refer to the file "copyright.html"
  20.  * for further important copyright and licensing information.
  21.  *
  22.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
  23.  * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
  24.  * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
  25.  * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
  26.  * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
  27.  * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
  28.  *
  29.  */
  30.  
  31. package java.text;
  32.  
  33. /**
  34.  * class CompactATypeArray : use only on primitive data types
  35.  * Provides a compact way to store information that is indexed by Unicode
  36.  * values, such as character properties, types, keyboard values, etc.This
  37.  * is very useful when you have a block of Unicode data that contains
  38.  * significant values while the rest of the Unicode data is unused in the
  39.  * application or when you have a lot of redundance, such as where all 21,000
  40.  * Han ideographs have the same value.  However, lookup is much faster than a
  41.  * hash table.
  42.  * A compact array of any primitive data type serves two purposes:
  43.  * <UL type = round>
  44.  *     <LI>Fast access of the indexed values.
  45.  *     <LI>Smaller memory footprint.
  46.  * </UL>
  47.  * A compact array is composed of a index array and value array.  The index
  48.  * array contains the indicies of Unicode characters to the value array.
  49.  *
  50.  * @see        CompactByteArray
  51.  * @see        CompactIntArray
  52.  * @see        CompactShortArray
  53.  * @see        CompactStringArray
  54.  * @version    1.9 10/28/97
  55.  * @author     Helena Shih
  56.  */
  57. final class CompactCharArray implements Cloneable{
  58.  
  59.     /**
  60.      * The total number of Unicode characters.
  61.      */
  62.     public static  final int UNICODECOUNT =65536;
  63.  
  64.     /**
  65.      * Default constructor for CompactCharArray, the default value of the
  66.      * compact array is '\u0000'.
  67.      */
  68.     public CompactCharArray()
  69.     {
  70.         this('\u0000');
  71.     }
  72.  
  73.     /**
  74.      * Contructor for CompactCharArray.
  75.      * @param defaultValue the default value of the compact array.
  76.      */
  77.     public CompactCharArray(char defaultValue)
  78.     {
  79.         int i;
  80.         values = new char[UNICODECOUNT];
  81.         indices = new short[INDEXCOUNT];
  82.         for (i = 0; i < UNICODECOUNT; ++i) {
  83.             values[i] = defaultValue;
  84.         }
  85.         for (i = 0; i < INDEXCOUNT; ++i) {
  86.             indices[i] = (short)(i<<BLOCKSHIFT);
  87.         }
  88.         isCompact = false;
  89.     }
  90.  
  91.     /**
  92.      * Constructor for CompactCharArray.
  93.      * @param indexArray the indicies of the compact array.
  94.      * @param newValues the values of the compact array.
  95.      * @exception IllegalArgumentException If the index is out of range.
  96.      */
  97.     public CompactCharArray(short indexArray[], char newValues[])
  98.     {
  99.         int i;
  100.         if (indexArray.length != INDEXCOUNT)
  101.             throw new IllegalArgumentException("Index out of bounds.");
  102.         for (i = 0; i < INDEXCOUNT; ++i) {
  103.             short index = indexArray[i];
  104.             if ((index < 0) || (index >= newValues.length+BLOCKCOUNT))
  105.                 throw new IllegalArgumentException("Index out of bounds.");
  106.         }
  107.         indices = indexArray;
  108.         values = newValues;
  109.     }
  110.  
  111.     /**
  112.      * Get the mapped value of a Unicode character.
  113.      * @param index the character to get the mapped value with
  114.      * @return the mapped value of the given character
  115.      */
  116.    public char elementAt(char index) // parameterized on short
  117.     {
  118.         return (values[(indices[index >> BLOCKSHIFT] & 0xFFFF)
  119.                        + (index & BLOCKMASK)]);
  120.     }
  121.  
  122.     /**
  123.      * Set a new value for a Unicode character.
  124.      * Set automatically expands the array if it is compacted.
  125.      * @param index the character to set the mapped value with
  126.      * @param value the new mapped value
  127.      */
  128.     public void setElementAt(char index, char value)
  129.     {
  130.         if (isCompact)
  131.             expand();
  132.         values[(int)index] = value;
  133.     }
  134.  
  135.     /**
  136.      * Set new values for a range of Unicode character.
  137.      * @param start the starting offset of the range
  138.      * @param end the ending offset of the range
  139.      * @param value the new mapped value
  140.      */
  141.     public void setElementAt(char start, char end, char value)
  142.     {
  143.         int i;
  144.         if (isCompact) {
  145.             expand();
  146.         }
  147.         for (i = start; i <= end; ++i) {
  148.             values[i] = value;
  149.         }
  150.     }
  151.  
  152.     /**
  153.       *Compact the array.
  154.       */
  155.     public void compact()
  156.     {
  157.         if (isCompact == false) {
  158.             char[] tempIndex;
  159.             int    tempIndexCount;
  160.             char[] tempArray;
  161.             short  iBlock, iIndex;
  162.  
  163.             // make temp storage, larger than we need
  164.             tempIndex = new char[UNICODECOUNT];
  165.             // set up first block.
  166.             tempIndexCount = BLOCKCOUNT;
  167.             for (iIndex = 0; iIndex < BLOCKCOUNT; ++iIndex) {
  168.                 tempIndex[iIndex] = (char)iIndex;
  169.             }; // endfor (iIndex = 0; .....)
  170.             indices[0] = (short)0;
  171.  
  172.             // for each successive block, find out its first
  173.             // position in the compacted array
  174.             for (iBlock = 1; iBlock < INDEXCOUNT; ++iBlock) {
  175.                 int     newCount, firstPosition, block;
  176.                 block = iBlock<<BLOCKSHIFT;
  177.                 if (DEBUGSMALL) if (block > DEBUGSMALLLIMIT) break;
  178.                 firstPosition = FindOverlappingPosition(block, tempIndex,
  179.                                                         tempIndexCount);
  180.  
  181.                 newCount = firstPosition + BLOCKCOUNT;
  182.                 if (newCount > tempIndexCount) {
  183.                     for (iIndex = (short)tempIndexCount;
  184.                          iIndex < newCount;
  185.                          ++iIndex) {
  186.                         tempIndex[iIndex] = (char)
  187.                                             (iIndex - firstPosition + block);
  188.                     } // endfor (iIndex = tempIndexCount....)
  189.                     tempIndexCount = newCount;
  190.                 } // endif (newCount > tempIndexCount)
  191.                 indices[iBlock] = (short)firstPosition;
  192.             } // endfor (iBlock = 1.....)
  193.  
  194.             // now allocate and copy the items into the array
  195.             tempArray = new char[tempIndexCount];
  196.             for (iIndex = 0; iIndex < tempIndexCount; ++iIndex) {
  197.                 tempArray[iIndex] = values[tempIndex[iIndex]];
  198.             }
  199.             values = null;
  200.             values = tempArray;
  201.             isCompact = true;
  202.         } // endif (isCompact != false)
  203.     }
  204.  
  205.     /** For internal use only.  Do not modify the result, the behavior of
  206.       * modified results are undefined.
  207.       */
  208.     public short getIndexArray()[]
  209.     {
  210.         return indices;
  211.     }
  212.     /** For internal use only.  Do not modify the result, the behavior of
  213.       * modified results are undefined.
  214.       */
  215.     public char getStringArray()[]
  216.     {
  217.         return values;
  218.     }
  219.     /**
  220.      * Overrides Cloneable
  221.      */
  222.     public Object clone()
  223.     {
  224.         try {
  225.             CompactCharArray other = (CompactCharArray) super.clone();
  226.             other.values = (char[])values.clone();
  227.             other.indices = (short[])indices.clone();
  228.             return other;
  229.         } catch (CloneNotSupportedException e) {
  230.             throw new InternalError();
  231.         }
  232.     }
  233.     /**
  234.      * Compares the equality of two compact array objects.
  235.      * @param obj the compact array object to be compared with this.
  236.      * @return true if the current compact array object is the same
  237.      * as the compact array object obj; false otherwise.
  238.      */
  239.     public boolean equals(Object obj) {
  240.         if (obj == null) return false;
  241.         if (this == obj)                      // quick check
  242.             return true;
  243.         if (getClass() != obj.getClass())         // same class?
  244.             return false;
  245.         CompactCharArray other = (CompactCharArray) obj;
  246.         for (int i = 0; i < UNICODECOUNT; i++) {
  247.             // could be sped up later
  248.             if (elementAt((char)i) != other.elementAt((char)i))
  249.                 return false;
  250.         }
  251.         return true; // we made it through the guantlet.
  252.     }
  253.     /**
  254.      * Generates the hash code for the compact array object
  255.      */
  256.  
  257.     public int hashCode() {
  258.         int result = 0;
  259.         int increment = Math.min(3, values.length/16);
  260.         for (int i = 0; i < values.length; i+= increment) {
  261.             result = result * 37 + values[i];
  262.         }
  263.         return result;
  264.     }
  265.     // --------------------------------------------------------------
  266.     // package private
  267.     // --------------------------------------------------------------
  268.     public void writeArrays()
  269.     {
  270.         int i;
  271.         int cnt = ((values.length > 0) ?
  272.                    values.length :
  273.                    (values.length + UNICODECOUNT));
  274.         System.out.println("{");
  275.         for (i = 0; i < INDEXCOUNT-1; i++)
  276.         {
  277.             System.out.print("(short)"
  278.                              + (int)((getIndexArrayValue(i) >= 0) ?
  279.                                      (int)getIndexArrayValue(i) :
  280.                                      (int)(getIndexArrayValue(i)+UNICODECOUNT))
  281.                              + ", ");
  282.             if (i != 0)
  283.                 if (i % 10 == 0)
  284.                     System.out.println();
  285.         }
  286.         System.out.println("(short)" +
  287.                            (int)((getIndexArrayValue(INDEXCOUNT-1) >= 0) ?
  288.                                  (int)getIndexArrayValue(i) :
  289.                                  (int)(getIndexArrayValue(i)+UNICODECOUNT)) +
  290.                            " }");
  291.         System.out.println("{");
  292.         for (i = 0; i < cnt-1; i++)
  293.         {
  294.             System.out.print("(char)" + (int)getArrayValue(i) + ", ");
  295.             if (i != 0)
  296.                 if (i % 10 == 0)
  297.                     System.out.println();
  298.         }
  299.         System.out.println("(char)" + (int)getArrayValue(cnt-1) + " }");
  300.     }
  301.  
  302.     // Print char Array  : Debug only
  303.     public void printIndex(short start, short count)
  304.     {
  305.         int i;
  306.         for (i = start; i < count; ++i)
  307.         {
  308.             System.out.println(i + " -> : "
  309.                                + (int)((indices[i] >= 0) ? indices[i]
  310.                                        : indices[i] + UNICODECOUNT));
  311.         }
  312.         System.out.println();
  313.     }
  314.  
  315.     public void printPlainArray(int start,int count, char[] tempIndex)
  316.     {
  317.         int iIndex;
  318.         if (tempIndex != null)
  319.         {
  320.             for (iIndex     = start; iIndex < start + count; ++iIndex)
  321.             {
  322.                 System.out.print(" " + (int)getArrayValue(tempIndex[iIndex]));
  323.             }
  324.         }
  325.         else
  326.         {
  327.             for (iIndex = start; iIndex < start + count; ++iIndex)
  328.             {
  329.                 System.out.print(" " + (int)getArrayValue(iIndex));
  330.             }
  331.         }
  332.         System.out.println("    Range: start " + start + " , count " + count);
  333.     }
  334.  
  335.     // --------------------------------------------------------------
  336.     // private
  337.     // --------------------------------------------------------------
  338.     /**
  339.       * Expanding takes the array back to a 65536 element array.
  340.       */
  341.     private void expand()
  342.     {
  343.         int i;
  344.         if (isCompact) {
  345.             char[]  tempArray;
  346.             tempArray = new char[UNICODECOUNT];
  347.             for (i = 0; i < UNICODECOUNT; ++i) {
  348.                 tempArray[i] = elementAt((char)i);
  349.             }
  350.             for (i = 0; i < INDEXCOUNT; ++i) {
  351.                 indices[i] = (short)(i<<BLOCKSHIFT);
  352.             }
  353.             values = null;
  354.             values = tempArray;
  355.             isCompact = false;
  356.         }
  357.     }
  358.  
  359.     // # of elements in the indexed array
  360.     private short capacity()
  361.     {
  362.         return (short)values.length;
  363.     }
  364.  
  365.     private char getArrayValue(int n)
  366.     {
  367.         return values[n];
  368.     }
  369.  
  370.     private short getIndexArrayValue(int n)
  371.     {
  372.         return indices[n];
  373.     }
  374.  
  375.     private int
  376.     FindOverlappingPosition(int start, char[] tempIndex, int tempIndexCount)
  377.     {
  378.         int i;
  379.         short j;
  380.         short currentCount;
  381.  
  382.         if (DEBUGOVERLAP && start < DEBUGSHOWOVERLAPLIMIT) {
  383.             printPlainArray(start, BLOCKCOUNT, null);
  384.             printPlainArray(0, tempIndexCount, tempIndex);
  385.         }
  386.         for (i = 0; i < tempIndexCount; i += BLOCKCOUNT) {
  387.             currentCount = (short)BLOCKCOUNT;
  388.             if (i + BLOCKCOUNT > tempIndexCount) {
  389.                 currentCount = (short)(tempIndexCount - i);
  390.             }
  391.             for (j = 0; j < currentCount; ++j) {
  392.                 if (values[start + j] != values[tempIndex[i + j]]) break;
  393.             }
  394.             if (j == currentCount) break;
  395.         }
  396.         if (DEBUGOVERLAP && start < DEBUGSHOWOVERLAPLIMIT) {
  397.             for (j = 1; j < i; ++j) {
  398.                 System.out.print(" ");
  399.             }
  400.             printPlainArray(start, BLOCKCOUNT, null);
  401.             System.out.println("    Found At: " + i);
  402.         }
  403.         return i;
  404.     }
  405.  
  406.     private static  final int DEBUGSHOWOVERLAPLIMIT = 100;
  407.     private static  final boolean DEBUGTRACE = false;
  408.     private static  final boolean DEBUGSMALL = false;
  409.     private static  final boolean DEBUGOVERLAP = false;
  410.     private static  final int DEBUGSMALLLIMIT = 30000;
  411.     private static  final int BLOCKSHIFT =7;
  412.     private static  final int BLOCKCOUNT =(1<<BLOCKSHIFT);
  413.     private static  final int INDEXSHIFT =(16-BLOCKSHIFT);
  414.     private static  final int INDEXCOUNT =(1<<INDEXSHIFT);
  415.     private static  final int BLOCKMASK = BLOCKCOUNT - 1;
  416.  
  417.     private char[] values;  // char -> short (char parameterized short)
  418.     private short indices[];
  419.     private boolean isCompact;
  420. };
  421.